﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Activity.III
{
	/// <summary>
	/// Линейный однонаправленный список. 
	/// </summary>
	public class LinkedList
	{
		/// <summary>
		/// Первый элемент в списке.
		/// </summary>
		public LinkedListNode Head { get; private set; }

		/// <summary>
		/// Создать новый экземпляр списка.
		/// </summary>
		public LinkedList () {}

		/// <summary>
		/// Создать новый экземпляр списка.
		/// </summary>
		/// <param name="size">Размер списка.</param>
		public LinkedList (int size)
		{
			for (int i = 0; i < size; i++) AddFirst(null);
		}

		/// <summary>
		/// Количество элементов в списке.
		/// </summary>
		public int Count { get; private set; }

		/// <summary>
		/// Добавить значение в начало списка.
		/// </summary>
		/// <param name="value">Значение которое добавить.</param>
		public void AddFirst (object value)
		{
			AddNodeFirst(CreateNode(value));
		}

		/// <summary>
		/// Удалить первый элемент из списка.
		/// </summary>
		public void RemoveFirst ()
		{
			if (Head == null) return;
			Head = Head.Next;
			Count--;
		}

		/// <summary>
		/// Добавить новое значение после указанного значения в списке.
		/// Если указанное значение не найдено, то новое значение будет добавлено в начало списка.
		/// </summary>
		/// <param name="existing">Предшествующее значение в списке.</param>
		/// <param name="value">Новое значение.</param>
		public void AddAfter (object existing, object value)
		{
			var node = Find(existing);
			if (node != null) AddValueAfter(node, value);
			else AddFirst(value);
		}

		/// <summary>
		/// Удалить все элементы из списка удовлетворяющие критерию.
		/// </summary>
		/// <param name="predicate">Критерий удаления.</param>
		public void RemoveAll (Predicate<object> predicate)
		{
			LinkedListNode previous = null;
			// Проверяем каждый узел
			foreach (var node in GetNodes())
			{
				// Удаляем элемент если удовлетворяет критерию
				if (predicate(node.Value))
				{
					if (previous != null) RemoveAfter(previous);
					else RemoveFirst();
				}
				else
				{
					// Запоминаем текущий узел
					previous = node;
				}
			}
		}

		/// <summary>
		/// Сортировка списка.
		/// </summary>
		/// <param name="comparer">Алгоритм сравнения элементов списка.</param>
		public void Sort (IComparer comparer)
		{
			// Начинаем поиск с первого узла списка
			var x = Head;
			// Пробегаем по каждому узлу в списке
			for (int i = 0; i < Count; i++)
			{
				// Сравниваем текущий элемент со всеми последующими элементами
				var y = x.Next;
				for (int j = i + 1; j < Count; j++)
				{
					// Меняем местами значения узлов если значение в узле 'х' больше значения в узле 'y'
					var compare = comparer.Compare(x.Value, y.Value);
					if (compare > 0) SwapNodeValue(x, y);
					// Двигаемся к следующему узлу
					y = y.Next;
				}
				// Двигаемся к следующему узлу
				x = x.Next;
			}
		}

		/// <summary>
		/// Линейный поиск заданного элемента в списке.
		/// </summary>
		/// <param name="value">Значение которое необходимо найти.</param>
		/// <returns>Узел в котором хранится заданное значение если таковой имеется; в противном случае null.</returns>
		public LinkedListNode Find (object value)
		{
			// Начинаем поиск с первого узла списка
			var retVal = Head;
			// Выполняем поиск до тех пор пока в списке есть элементы
			while (retVal != null)
			{
				// Если значение узла совпадает со искомым значением, то возвращаем этот узел
				if (Equals(retVal.Value, value))
					return retVal;

				// В противном случае двигаемся к следующему узлу
				retVal = retVal.Next;
			}
			// При неудачном поиске возвращаем null.
			return null;
		}

		/// <summary>
		/// Получить коллекцию всех значений в списке.
		/// </summary>
		public IEnumerable<object> GetValues ()
		{
			foreach (var node in GetNodes())
				yield return node.Value;
		}

		/// <summary>
		/// Получить коллекцию всех узлов в списке.
		/// </summary>
		public IEnumerable<LinkedListNode> GetNodes ()
		{
			var node = Head;
			if (node == null) yield break;
			// Выполняем пока не дойдем до последнего элемента в списке
			while (node.Next != node)
			{
				yield return node;
				node = node.Next;
			}
			// Последний элемент списка
			yield return node;
		}

		/// <summary>
		/// Добавить узел в начало списка.
		/// </summary>
		/// <param name="value">Узел который должен стать первым узлом в списке.</param>
		private void AddNodeFirst (LinkedListNode value)
		{
			if (Head == null) value.Next = value;
			else value.Next = Head;
			Head = value;
			Count++;
		}

		/// <summary>
		/// Добавить новое значение после указанного узла.
		/// </summary>
		/// <param name="existing">Предшествующий узел в списке.</param>
		/// <param name="value">Новое значение.</param>
		private void AddValueAfter (LinkedListNode existing, object value)
		{
			AddNodeAfter(existing, CreateNode(value));
		}

		/// <summary>
		/// Добавить новый узел после указанного узла.
		/// </summary>
		/// <param name="existing">Предшествующий узел в списке.</param>
		/// <param name="value">Новый узел.</param>
		private void AddNodeAfter (LinkedListNode existing, LinkedListNode value)
		{
			var next = existing.Next;
			existing.Next = value;
			value.Next = next;
			Count++;
		}

		/// <summary>
		/// Удалить узел после указанного узла.
		/// </summary>
		/// <param name="existing">Предшествующий узел в списке.</param>
		private void RemoveAfter (LinkedListNode existing)
		{
			var next = existing.Next;
			if (next == null) return;
			existing.Next = next.Next;
			Count--;
		}

		/// <summary>
		/// Обменять значения узлов.
		/// </summary>
		private static void SwapNodeValue (LinkedListNode x, LinkedListNode y)
		{
			var t = x.Value;
			x.Value = y.Value;
			y.Value = t;
		}

		/// <summary>
		/// Создать новый экземпляр узла.
		/// </summary>
		/// <param name="value">Значение хранимое в узле.</param>
		/// <returns>Новый экземпляр узла.</returns>
		private static LinkedListNode CreateNode (object value)
		{
			return new LinkedListNode {Value = value};
		}
	}

	/// <summary>
	/// Узел линейного списка.
	/// </summary>
	public class LinkedListNode
	{
		/// <summary>
		/// Значение хранимое в узле.
		/// </summary>
		public object Value { get; set; }

		/// <summary>
		/// Следующий узел в списке.
		/// </summary>
		public LinkedListNode Next { get; internal set; }
	}
}
